全排列
描述
给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。
输入描述：
输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。
输出描述：
输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义： 已知S = s1s2...sk , T = t1t2...tk，则S < T 等价于，存在p (1 <= p <= k)，使得 s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。 每组样例输出结束后要再输出一个回车。
示例1
输入：
abc

输出：
abc
acb
bac
bca
cab
cba

//递归
#include<bits/stdc++.h>
using namespace std;

const int MAXN=10;

bool visit[MAXN];//元素是否存在
char sequence[MAXN];//存储单个排列

void GetPermutation(string str,int index){//index递归深度
    if(index==str.size()){
        for(int i=0;i<str.size();++i){
            printf("%c",sequence[i]);
        }
        printf("\n");
    }
    for(int i=0;i<str.size();++i){
        if(visit[i]){
            continue;
        }
        visit[i]=true;
        sequence[index]=str[i];
        GetPermutation(str,index+1);
        visit[i]=false;
    }
}

int main(){
    string str;
    while(cin>>str){
        //sort(str.begin(),str.end());
        GetPermutation(str,0);
        printf("\n");
    }
}

//非递归
#include<bits/stdc++.h>
using namespace std;

bool GetNextPermutation(string &str){
    int n=str.size();
    int index=n-2;
    while(index>=0&&str[index]>=str[index+1]){//52431找到2
        index--;
    }
    if(index<0){
        return false;
    }
    for(int i=n-1;i>index;--i){//找到比str[index]大的数中最小的,53421
        if(str[index]<str[i]){
            swap(str[index],str[i]);
            break;
        }
    }
    reverse(str.begin()+index+1,str.end());//53124
    return true;
}

int main(){
    string str;
    while(cin>>str){
        sort(str.begin(),str.end());
        do{
            cout<<str<<endl;
        }while(GetNextPermutation(str));//输出下一个全排列数
        cout<<endl;
    }
    return 0;
}

//自带，algorithm
#include<bits/stdc++.h>
using namespace std;

int main(){
    string str;
    while(cin>>str){
        sort(str.begin(),str.end());
        do{
            cout<<str<<endl;
        }while(next_permutation(str.begin(),str.end()));//后可添加比较函数
        cout<<endl;
    }
    return 0;
}

